package nowcoder;

public class UglyNumber {

	public int GetUglyNumber_Solution(int index) {
		if(index <= 0)
            return 0;
		
		int[] uglyNumber = new int[index];
		uglyNumber[0] = 1;
		int count = 1;
		
		int multiplyTwo, multiplyThree, multiplyFive;
		while(count < index) {
			multiplyTwo = 0;
			multiplyThree = 0;
			multiplyFive = 0;
			
			multiplyTwo = getMini(2, uglyNumber, count);
			multiplyThree = getMini(3, uglyNumber, count);
			multiplyFive = getMini(5, uglyNumber, count);
			
			uglyNumber[count] = minimumOfThree(multiplyTwo, multiplyThree, multiplyFive);
			count++;
		}
		
		return uglyNumber[index - 1];
	}

	private int minimumOfThree(int multiplyTwo, int multiplyThree, int multiplyFive) {
		if(multiplyTwo < multiplyThree) {
			if(multiplyTwo < multiplyFive)
				return multiplyTwo;
			else
				return multiplyFive;
		}else {
			if(multiplyThree < multiplyFive)
				return multiplyThree;
			else
				return multiplyFive;
		}
	}

	private int getMini(int multiply, int[] uglyNumber, int count) {
		for(int i = 0; i < count; i++) {
			if(uglyNumber[i] * multiply > uglyNumber[count - 1])
				return uglyNumber[i] * multiply;
		}
		return 0;
	}
	
}
